#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

bool IsPalin(string &str){
	int i=0;
	int j=str.length()-1;
	while(i<j){
		if(str[i] != str[j])
			return false;
		++i;
		--j;
	}
	return true;
}


int partition(string s) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	if(s.length() == 0)
		return 0;
	if(s.length() == 1){
		return 0;
	}

	vector<vector<vector<string> > > tilAnswer;
	vector<string> temp;
	temp.push_back(s.substr(0,1));
	vector<vector<string> > zeroAnswer;
	zeroAnswer.push_back(temp);
	tilAnswer.push_back(zeroAnswer);

	for(int i=1; i<s.length(); ++i){
		vector<vector<string > > curAnswer;
		// for each last one
		for(int j=i; j>=0; --j){
			string last = s.substr(j, i-j+1);
			if(IsPalin(last)){
				// for each tilAnswer[j-1]
				if(j>0){
					for(int k=0; k<tilAnswer[j-1].size(); ++k){
						vector<string> answer = tilAnswer[j-1][k];
						answer.push_back(last);
						curAnswer.push_back(answer);
					}
				}
				else{
					vector<string> answer;
					answer.push_back(last);
					curAnswer.push_back(answer);
				}
				
			}
		}
		tilAnswer.push_back(curAnswer);
	}

	int min = 0x7FFFFFFF;
	for(int i=0; i<tilAnswer[s.length()-1].size(); ++i){
		int cur = tilAnswer[s.length()-1][i].size();
		if( cur < min)
			min = cur;
	}


	return min-1;
}


int main()
{
	partition("abababababababababab");

	return 0;
}